package poj1458;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
/*
POJ1458
输入样例：
abcfbc         abfcab
programming    contest 
abcd           ad
ABCPDSFJGODIHJOFDIUSHGD	    OSDIHGKODGHBLKSJBHKAGHI

 * */
public class Main {
	public static void main(String[] args) {
		 Scanner sc = new Scanner(System.in);
	     
	     String inputStr1;
	     String inputStr2;
	     while (sc.hasNext()) {
	        inputStr1 = sc.next();
            inputStr2 = sc.next();
            System.out.println(lcs2(inputStr1.toCharArray(), inputStr2.toCharArray()));
        }
        
	}

	
	//最长公共子序列LCS（模板）
	static int maxn = 1000;
	static int[][] dp = new int[maxn][maxn];
    static int lcs(char[] s1, char[] s2) {   
        int len1 = s1.length;
        int len2 = s2.length;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
            	//字符串实际下标从0开始
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[len1][len2];
    }
    
    //最长公共子序列LCS，记录LCS和字符位置并输出
    static int[][] b = new int[maxn][maxn];   //b数组记录LCS位置
    static int lcs2(char[] s1, char[] s2) {   
        int len1 = s1.length;
        int len2 = s2.length;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
            	//字符串实际下标从0开始
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    b[i][j] = 1;  //对应伪代码，1表示箭头为左上
                } else if(dp[i-1][j]>=dp[i][j-1]){
                    dp[i][j] = dp[i-1][j];
                    b[i][j] = 2;  //对应伪代码，2表示箭头为上
                } else {
                	dp[i][j] = dp[i][j-1];
                	b[i][j] = 3;  //对应伪代码，3表示箭头为左
                }
            }
        }
        
        //根据b数组获取LCS字符串
        LinkedList<Character> strLcs = new LinkedList<Character>();
        //s1中lcs的下标
        LinkedList<Integer> s1Lcs = new LinkedList<Integer>();
        //s2中lcs的下标
        LinkedList<Integer> s2Lcs = new LinkedList<Integer>();
        for(int i = len1,j = len2;i >= 1 && j >= 1; ) {
        	if(b[i][j]==1) {
        		i--;
        		j--;
        		//字符串实际下标从0开始
        		strLcs.addLast(s1[i]);
        		s1Lcs.addLast(i);
        		s2Lcs.addLast(j);
        	}else if(b[i][j]==2) {
        		i--;
        	}else {
        		j--;
        	}
        }
        
        //输出dp数组
        System.out.println("dp数组：");
        for(int i=0;i<=len2;i++) {
        	if(i == 0)
        		System.out.printf("    ");
        	else
        		System.out.printf("%c ",s2[i-1]);
        }
        System.out.println();
        for(int i = 0;i <= len1;i++) {
        	if(i == 0)
        		System.out.printf(" [");
        	else
        		System.out.printf("%c[",s1[i-1]);
        	for(int j = 0; j<=len2; j++) {
        		
        		System.out.printf("%d,", dp[i][j]);
        	}
        	System.out.println("]");
        }
        
        //输出b数组
        System.out.println("b数组：");
        for(int i=0;i<=len2;i++) {
        	if(i == 0)
        		System.out.printf("    ");
        	else
        		System.out.printf("%c ",s2[i-1]);
        }
        System.out.println();
        for(int i = 0;i <= len1;i++) {
        	if(i == 0)
        		System.out.printf(" [");
        	else
        		System.out.printf("%c[",s1[i-1]);
        	for(int j = 0; j<=len2; j++) {
        		
        		System.out.printf("%d,", b[i][j]);
        	}
        	System.out.println("]");
        }
        
        
        //输出LCS字符串
        System.out.println("LCS字符串：");
        while(!strLcs.isEmpty()) {
        	System.out.printf("(%c,s1[%d],s2[%d]),", strLcs.pollLast(),s1Lcs.pollLast(),s2Lcs.pollLast());
        }
        System.out.println();
        
        return dp[len1][len2];
    }
    
}
